#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/11/26 17:40|17:40
# @Author  : yangdingyi
# @File    : 旋转数组
# @Software: PyCharm


class Solution:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # 1. O(n) gcd(n,k)
        n = len(nums)
        k %= n
        if k <= 0 or n <= 1:
            return

        def gcd(x, y):
            if x < y:
                x, y = y, x
            if y == 0:
                return 0
            while x % y != 0:
                x, y = y, x % y
            return y
        e = gcd(n, k)
        for i in range(e):
            xx, ii, iii = nums[i], i, (i+k) % n
            while iii != i:
                xx, nums[iii] = nums[iii], xx
                ii, iii = iii, (iii+k) % n
            nums[i] = xx
        # 2. n 次不对，还要考虑gcd(n,k)
        # n = len(nums)
        # k %= n
        # i, s, x = 0, 0, nums[0]
        # while s < n:
        #     i = (i+k) % n
        #     nums[i], x = x, nums[i]
        #     s += 1
        # nums[i] = x


solve = Solution()
nums = [1, 2, 3, 4, 5, 6]
k = 2


